SL4 Instance Based Learning
Published:
Instance Based Learning
1. KNN - K-nearest neighbor
1. Two Hyper-parameters:
- Distance function
- Number of K
domain knowledge needed to decide these two hyper-parameters
2. 1-NN vs KNN vs linear Regression:
| Type | Time(learn) | Time(query) | Space(learn) | Space(query) |
|---|---|---|---|---|
| 1-NN | 1 | logN | N | 1 |
| K-NN | 1 | logN + k | N | 1 |
| Linear Regression | N | 1 | 1(two params m,b) | 1 |
3. Preference Bias of KNN:
- Locality —> assume near points are similar —> distance function
- Smoothness —> averages
- All feature matter equally —> same polynomial
2. Curse of Dimensionality
1.Definition
As number of features or dimensions grows, the amount of data needed to generalize accurately grows exponentially